Permutation Search Methods are Efficient, Yet Faster Search is Possible

摘要

We survey permutation-based methods for approximate k-nearest neighborsearch. In these methods, every data point is represented by a ranked list ofpivots sorted by the distance to this point. Such ranked lists are calledpermutations. The underpinning assumption is that, for both metric andnon-metric spaces, the distance between permutations is a good proxy for thedistance between original points. Thus, it should be possible to efficientlyretrieve most true nearest neighbors by examining only a tiny subset of datapoints whose permutations are similar to the permutation of a query. We furthertest this assumption by carrying out an extensive experimental evaluation wherepermutation methods are pitted against state-of-the art benchmarks (themulti-probe LSH, the VP-tree, and proximity-graph based retrieval) on a varietyof realistically large data set from the image and textual domain. The focus ison the high-accuracy retrieval methods for generic spaces. Additionally, weassume that both data and indices are stored in main memory. We findpermutation methods to be reasonably efficient and describe a setup where thesemethods are most useful. To ease reproducibility, we make our software and datasets publicly available.